package lbj.cyw.dp;
/*
* Offer49. 丑数
*
* *******三指针解法
* */
public class Offer49nthUglyNumber {
    public int nthUglyNumber(int n) {
      int p2,p3,p5;
      p3=p5=p2=0;
      int[] dp=new int[n];
      dp[0]=1;
      for(int i=1;i<n;i++){
          int num2=2*dp[p2];
          int num3=3*dp[p3];
          int num5=5*dp[p5];
          dp[i]=Math.min(Math.min(num2,num3),num5);
          if(dp[i]==num2)p2++;
          if(dp[i]==num3)p3++;
          if(dp[i]==num5)p5++;
      }
      return dp[n-1];
    }
}
